package com.solming.leetcode.question;

import java.util.Stack;

//请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
//
//实现 MyQueue 类：
//
//void push(int x) 将元素 x 推到队列的末尾
//int pop() 从队列的开头移除并返回元素
//int peek() 返回队列开头的元素
//boolean empty() 如果队列为空，返回 true ；否则，返回 false
//
//
//说明：
//
//你只能使用标准的栈操作 —— 也就是只有push to top,peek/pop from top,size, 和is empty操作是合法的。
//你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
//
//
//进阶：
//
//你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/implement-queue-using-stacks
public class MyQueue232 {

    Stack<Integer> s1 ;
    Stack<Integer> s2 ;

    public MyQueue232() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(Integer x) {
        s1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek();
        return s2.pop();
    }

    /** Get the front element. */
//    public int peek() {
//        while (!s1.empty()){
//            s2.push(s1.pop());
//        }
//        return s2.peek();
//    }
    public int peek() {
        //判断 s2 的顺序先拿完，再进行 s1 压入 s2、
        if (s2.isEmpty())
            // 把 s1 元素压入 s2
            while (!s1.isEmpty())
                s2.push(s1.pop());
        return s2.peek();
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.empty()&&s2.empty();
    }


    public static void main(String[] args) {
        MyQueue232 queue232 = new MyQueue232();
        queue232.push(null);
        queue232.push(1);
        queue232.push(2);
        queue232.push(3);
        queue232.push(4);
        System.out.println(queue232.pop());
        queue232.push(5);
        System.out.println(queue232.pop());
        System.out.println(queue232.pop());
        System.out.println(queue232.pop());
        System.out.println(queue232.pop());
    }
}
